Erzurum'da, Kars Kapı Caddesi üzerindeki türbe yol seviyesinden yaklaşık iki metre yüksekliğinde, Mahmut Paşa Mezarlığı içerisinde yer almaktadır. Türbenin yola bakan cephesi üzerindeki 0,44x 0, 68 metre ölçülerindeki mermer kitabede Hazelbina, Bazezit mutasarrıfı el-merhum-ül mağfur, Mahmut Paşa ve pederi Abdülfettah Bey merkad-ı şerifleridir. Ruh-i şerifleri için el-fatiha sene 1209 H. 1794 ibaresi geçmektedir. Buradan türbenin 1794'te inşa edildiği veya tamir ettirildiği düşünülmektedir. Türbenin içerisindeki alçak çerçeveli iki mezardan 1123 H. 1711 M. tarihli olan babası Abdülfettah Bey'e, 1181 H. 1767 M. ise Mahmut Paşa'ya aittir. 

Baldaken formda inşa edilen türbe 4,06 x 4,06 metre ebatlarında kare planda düzenlenmiştir. Türbeyi oluşturan köşelerdeki payeler birbirlerine sivri kemerler ile bağlanmıştır. Kemer başlangıçlarında mukarnas dizisi, saçak seviyesinde kaş kemerli olarak verilen dekoratif niş dizisi alanı dolanmakta, saçak ise üstte düz bir silme ile son bulmaktadır. Baldaken türbenin üstü yukarı doğru sivrilen bir kubbe örtülmüştür.