Баян-Өлгий аймаг байгуулагдахаас өмнө тус аймгийн нутагт Ховд аймгийн прокурорын харьяа 3 орон тоотой хэсгийн прокурор ажиллаж байсан нь Баян- Өлгий аймгийн прокурорын байгууллагын үндэс суурь болжээ.

1940 оны 8 дугаар сарын 20-нд Баян-Өлгий аймаг байгуулагдсаны дараа буюу 1940 оны 10 дугаар сард Улсын прокурорын 50 дугаар тушаалаар Баян-Өлгий аймгийн прокурор газрыг анх байгуулж, прокурор 1, мөрдөн байцаагч 3, нарийн бичгийн дарга 1, зарлага 1, бүгд 6 орон тоотойгоор үйл ажиллагаагаа явуулж эхэлсэн түүхтэй.

Прокурорын ерөнхий хяналт, урьдчилан сэргийлэх ажилтай холбогдуулан 1962 оноос эхлэн аймгийн прокурор газарт ерөнхий хяналтын туслах прокурорын, 1970 онд шүүхийн хяналтын туслах прокурорын, 1982 онд тусгай хяналтын ажил эрхэлсэн туслахын орон тоо бий болж байжээ. Өдгөө тус аймгийн прокурорын газар нь 21 прокурор, ажилтны орон тоотой ажиллаж байна.