Pendirian benteng Kuto Besak berawal dari gagasan Sultan Mahmud Badaruddin I dan didirikan pada masa Sultan Mahmud Bahauddin  pada tahun 1780, selesai tahun 1797 M. Telah dikenal arsitek yang membidangi pendirian dan pengawasan benteng adalah orang cina. Pada perkembangan selanjutnya, bagian pintu gerbang utama dan beberapa bangunan di dalam benteng dibangun pada masa kolonial belanda.

Benteng Kuto Besak memiliki denah berbentuk persegi panjang dan menghadap ke arah tenggara serta posisinya tepat berada di pinggiran Sungai Musi. Secara keseluruhan Benteng Kuto Besak berukuran 288,75 M x 183,75 M. Benteng Kuto Besak memiliki tembok keliling dengan bentuk dinding dan ketinggian masing-masing sisi berdeda-beda. Pada bagian dinding benteng sisi timur laut mempunyai ketebalan yang sama, sedangkan  ketinggian dinding bagian depan berukuran 12,39 M dan bagian dalam berukuran 13,04 M. Adanya perbedaan ketinggian pada dinding bagian depan dan dalam membentuk bidang miring yang landai. Selain itu pada dinding benteng sisi timur laut terdapat celah intai berbentuk persegi dengan bagian atas berbentuk lengkungan.

Pada bagian tembok benteng sisi barat daya terdapat perbedaan dalam hal ketebalan, hal ini dikarenakan pada bagian tengahnya terdapat pintu gerbang. Perbedaan tersebut terlihat dari tembok benteng sisi barat daya bagian selatan memiliki bentuk bagian bawahnya lebih tebal dari pada bagian atas, yaitu 1,95 M dan 1,25 M, akan tetapi bagian dalam dan luar tembok mempunyai ketinggian yang sama yaitu  2,5 M. Tembok benteng  sisi barat daya bagian utara memiliki bentuk yang sama dengan bagian selatan, yaitu terdapat perbedaan ketebalan antara bagian bawah 2,35 M dan atas 1,95 M. Hal serupa juga terjadi pada tembok benteng sisi barat laut memiliki bentuk yang hampir sama dengan tembok sisi barat daya bagian selatan. Adapun tebal tembok bagian bawah adalah 1,6 m dan bagian atas 1,15 m dengan ketinggian dinding 2,25 m.

Pada setiap sudut benteng terdapat bastion, yaitu terletak pada sudut utara, selatan, timur dan barat . Bastion yang terletak di sudut utara, selatan dan timur memiliki bentuk trapesium, sedangkan di sudut barat berbentuk segi lima. Benteng Kuto Besak mempunyai 3 buah pintu, yaitu terletak pada sisi tenggara, timur laut dan barat laut. Pada saat ini yang masih tersisa adalah pintu di sebelah sisi tenggara yang merupakan pintu gerbang utama dan sisi barat laut.