აღსრულების ეროვნული ბიუროს ისტორია 2000 წლიდან აითვლება, მანამდე არსებობდნენ სასამართლო აღმასრულებლები, რომლებიც განთავსებულნი იყვნენ სასამართლოს შენობაში. სასამართლო აღმასრულებლები ახდენდენ სასამართლო გადაწყვეტილებების სისრულეში მოყვანას (აღსრულებას). სასამართლო აღმასრულებლებს საქმეები თბილისის უბნების მიხედვით ჰქონდათ განაწილებული.
თბილისის ბიურო, როგორც ერთიანი სისტემა, უბნების გარეშე 2002 წელს შეიქმნა.
სააღსრულებო ბიუროს, როგორც ცალკე სამსახურის შექმნა, 1999 წლის სააღსრულებო წარმოებათა შესახებ კანონის ძალაში შესვლამ განაპირობა. სააღსრულებო დეპარტამენტს კონტროლს უწევდა იუსტიციის სამინისტრო, და იგი წარმოადგენდა იუსტიციის სამინისტროს სტრუქტურულ ერთეულს. სამსახურს ხელმძღვანელობდა დეპარტამენტის თავმჯდომარე, რომელსაც ჰყავდა ორი მოადგილე, მოადგილეებიდან, ერთი - აღმოსავლეთ, მეორე კი დასავლეთ საქართველოს ხელმძღვანელობდა. მათ დაქვემდებარებაში იყო სააღსრულებო წარმოების განყოფილება, სადაც ხდებოდა შემოსული განცხადებებისა და პრეტენზიების განხილვა და მასზე შესაბამის რეაგირება.
რაც შეეხება აღმასრულებლებს, ისინი კვლავ სასამართლო აღმასრულებლად იწოდებოდნენ. აღმასრულებლის საქმეები ცალკე კატეგორიებად არ იყო დაყოფილი. დღევანდელი სიტუაციისგან განსხვავებით, თითეულ აღმასრულებელს წარმოებაში ყველა კატეგორიის საქმე ჰქონდა.
სააღსრულებო ბიუროს ხელმძღვანელობდა ბიუროს უფროსი, რომელსაც თანამდებობაზე ნიშნავდა და ათავისუფლებდა იუსტიციის მინისტრი, სააღსრულებო დეპარტამენტის თავჯდომარის წარდგინებით.
სააღსრულებო დეპარტამენტთან ერთად არსებობა დაიწყო სააღსრულებო პოლიციამ, რომელიც აღმასრულებელთან ერთად გადაწყვეტილებების სისრულეში მოყვანას უწყობს ხელს.
სააღსრულებო პოლიციაში არსებობდა მოკვლევის ჯგუფი, რომლის ფუნქციები დღევანდელი კანონმდებლობით მინიჭებული აქვს საქართველოს პროკურატურას.
2008 წლის პირველი ოქტომბრიდან იუსტიციის სამინისტროს სააღსრულებო დეპარტამენტი აღსრულების ეროვნულ ბიუროდ ჩამოყალიბდა და საჯარო სამართლის იურიდიული პირი გახდა. სამსახურში მნიშვნელოვანი ცვლილებები დაიწყო. სისტემა უფრო გამჭირვალე და თანამედროვე სტანდარტების შესაბამისი გახდა. აღსრულების ეროვნული ბიუროს და მისი აღმასრულებლების პირდაპირი ინტერესი და მოტივაცია მოქალაქის დადასტურებული მოთხოვნის დაკმაყოფილება გახდა. საქმეთა კატეგორიების მიხედვით, სისტემა გადავიდა მომსახურების ფასიან მოდელზე, რაც უზრუნველყოფს მოქალაქეთა სწრაფ და ეფექტურ მომსახურებას.
წლების მანძილზე არსებული ოფისების პრობლემა ნაწილობრივ გადაწყდა - აღსრულების ეროვნულ ბიუროს და თბილისის სააღსრულებო ბიუროს შენობა გამოეყო.
ჩამოყალიბდა საერთაშოროსო ურთიერთობებიც - შვედეთის საერთაშორისო განვითარების სააგენტოსთან, ამერიკის იურისტთა ასოციაციასთან და გერმანიის ტექნიკური თანამშრომლობის საზოგადოებასთან პროექტების განხორციელება დაიწყო. ამ პროექტებით გათვალისწინებული იყო ექსპერტთა დახმარება სისტემის განვითარების სტრატეგიის შემუშავებაში, ტრენინგები აღსრულების თანამშრომლებისთვის. სასწავლო ვიზიტები შვედეთში, პრაქტიკული სახელმძღვანელოს მომზადება აღმასრულებლებისთვის, ასევე პრევენციული საინფორმაციო კამპანიის წარმოება.
2009 წლიდან შეიქმნა აღსრულების ეროვნულ ბიუროს ვებ-გვერდი - www.nbe.gov.ge . ვებ-გვერდზე სისტემატურად ქვეყნდება ინფორმაცია აუქციონების, მომსახურების, აღმასრულებელთა უფლება-მოვალეობის, კრედიტორის და მოვალის სამართლებრივი გარანტიების შესახებ. გარდა ამისა, მუშაობს საინფორმაციო ცენტრი - 2 749 649, რამაც კიდევ უფრო მეტად დახვეწა საზოგადოებასთან ურთიერთობა.
ამავე წლის ივნისიდან ფუნქციონირება დაიწყო კერძო აღმასრულებლის ინსტიტუტმა. მათ საქმიანობას კონტროლს უწევს იუსტიციის სამინისტრო, იგი გასცემს ლიცენზიებს კერძო პირებისათვის, რომლებიც დამოუკიდებლად, სახელმწიფო აღმასრულებლის იდენტური უფლებამოსილებებითა და საშუალებებით აღასრულებდნენ მათი აღსრულების ქვემდებარე გადაწყვეტილებებს (ძირთადად სამოქალაქო საქმეებზე). აღნიშნული ინსტიტუტის დახვეწა დღემდე მიმდინარეობს.
2009 წლის პირველი ოქტომბრიდან აღსრულების ეროვნულმა ბიურომ საქმის წარმოების ელექტრონულ პროგრამაზე მუშაობა დაიწყო. პროგრამის დახმარებით სააღსრულებო ბიუროს საქმიანობა მთლიანად ელექტრონული გახდა. ამასთან, მისი მეშვეობით ამა თუ იმ საქმის მსვლელობის შესახებ დეტალური ინფორმაციის მიღება კრედიტორსა და მოვალეს სახლიდან გაუსვლელად, ინტერნეტის საშუალებით შეუძლიათ. ელექტორნული პროგრამის მეშვეობით, ყველა განცხადება, ასვე საჩივარი, რომელიც აღსრულების ეროვნულ ბიუროში თუ მის ტერიტორიულ ორგანოებში შედის, ავტომატურად ტარდება ამ პროგრამაში.
2010 წლის 24 მაისს, გაიმართა ახალი სათაო ოფისის პრეზენტაცია და დღეისათვის საქართვველოს იუსტიციის სამინისტროს აღსრულების ეროვნული ბიუროს ირიდიული მისამართია: დ.აღმაშენებლის ხეივანი 10 კილომეტრი. იგი უახლესი აპარატურით არის აღჭურვილი და თანამედროვე სტანდარტებს სრულად აკმაყოფილებს. შენობაში აღსრულების ეროვნულ ბიუროსა და თბილისის სააღსრულებო ბიუროს თანამშრომლები განთავსდნენ.
აღსრულების ეროვნული ბიურო, საქართველოს მასშტაბით, 8 რეგიონალურ ოფისს ფლობს, რომელთა ევროპულ სტანდარტებზე გადასვლის პროცესი ამ დრომდე მიმდინარეობს. ახალი საოფისე შენობები ქვემო ქართლში, იმერეთში, გურიაში, შიდა ქართლსა და მცხეთა-მთიანეთში, სამეგრელო-ზემო სვანეთში, სამცხე-ჯავახეთსა, რაჭა ლეჩხუმისა და ქვემო სვანეთის, აჭარასა და კახეთში უკვე გაიხსნა.