Po ukończeniu studiów miał trudności ze znalezieniem odpowiedniej pracy na scenie i często był zmuszony podejmować prace dorywcze, aby uzupełnić swoje dochody.
Kariera sceniczna Kiedy Vereen miał 18 lat, w 1965 wystąpił na nowojorskiej scenie Off-off-Broadwayu w sztuce Bertolta Brechta i Langstona Hughesa Wyjątek i reguła / Syn marnotrawny w Greenwich Mews Theatre. W 1966 przebywał w Las Vegas, występując jako brat Ben w przedstawieniu Słodka dobroczynność w reżyserii Boba Fosse’a, z którym w latach 1967–68 odbył tournée. W 1968 powrócił do Nowego Jorku, aby zagrać Claude’a w musicalu Hair na Broadwayu. W 1972 za rolę Judasza Iskarioty w operze rockowej Andrew Lloyda Webbera i Tima Rice’a Jesus Christ Superstar został uhonorowany nagrodą Theatre World i był nominowany do Tony Award dla najlepszego aktora drugoplanowego w musicalu. W 1973 za tytułową rolę w musicalu Stephena Schwartza Pippin otrzymał nagrodę Drama Desk Award i Tony Award dla najlepszego aktora w musicalu. W 2002 zagrał w produkcji off-Broadwayowskiej Uniewinniony. W 2005 powrócił na Broadway jako Czarnoksiężnik z Oz w musicalu Stephena Schwartza Wicked.