Teatterissa Nayyar on näytellyt muun muassa losangelesilaisen Black Dahlia Theaterin näytelmässä Huck & Holden, josta hänet palkittiin Garland Awardilla vuonna 2007. Hän on esiintynyt Stratford-upon-Avonissa sijaitsevan Royal Shakespeare Companyn näytelmässä Turhaa lemmen touhua.