Kitabesine düşülen tarihe göre 1307 yılında inşa edilmiştir. Kesme taş ve moloz taştan malzemelerle inşa edilen Yıldızlı Han, 613 metrekarelik bir alana oturmaktadır. Han’ın alt katı Selçuklu mimarisinin özelliklerine uygun olarak kesme taş ile üst katı moloz taş ve tuğla malzeme kullanılarak inşa edilmiştir. Han’ın 52 bölümü vardır. Birinci katta kuyumcular, manifaturacılar, bakırcılar ve gümüşçüler bulunurken ikinci kat otel hizmeti vermek üzere planlanmıştır. 1916 Rus işgali sırasında yapı işgal kuvvetleri tarafından tahrip edilmiştir. 2000’li yılların başında bina harabe haline gelmiştir. Ön cephesi ve birkaç odası ayakta kalabilen Han, 2014 yılında kamulaştırılmıştır. 2015 yılında Muş Belediyesi, İl Kültür Turizm Müdürlüğü ortak çalışmalarıyla Han’ın restorasyonuna başlanmıştır. Restorasyon çalışması 2019 Ekim ayı itibariyle sürmektedir.

Birçok kaynakta Miralay Seyfi Bey tarafından yaptırıldığı kaydedilen Han hakkındaki tek akademik çalışmada kitabesinde yazılı adı Yoldüzler olarak yanlış okunmaktadır. Selçuklu dönemine ait olduğu bilinen yapının Osmanlı Devleti’nin son dönemlerinde kullanılan Miralay rütbesini taşıyan biri tarafından yaptırılmış olması mümkün gözükmemektedir. Ayrıca Hicri 1307 olarak okunan kitabe Miladi takvime çevrildiğinde yapım tarihi 1889 olacaktır. Bu da Selçuklu Devleti yıkıldıktan 500 yıl sonrasına denk gelmektedir. Kitabenin Osmanlı Devleti'nin döneminde yapılan büyük bir restorasyonu işaret ediyor olması muhtemeldir. Binanın diğer cephelerindeki kitabeler tahrip olduğundan daha net bir bilgiye ulaşılamamaktadır.