Cancer-associated fibroblasts (CAFs) in the stroma of solid tumors promote an immunosuppressive tumor microenvironment (TME) that drives resistance to therapies. The expression of the protease fibroblast activation protein (FAP) on the surface of CAFs has made FAP a target for the development of therapies to mitigate immunosuppression. Relatively few biologics have been developed for FAP and none have been developed that exploit the unique properties of Variable New Antigen Receptors (VNARs) from shark immunoglobulins. Through the direct immunization of a nurse shark with FAP, we created a large anti-FAP VNAR phage display library. This library allowed us to identify a suite of anti-FAP VNARs through traditional biopanning and by an in silico approach that did not require any affinity maturation. We investigated four VNAR-Fc fusion proteins for theranostic properties and found that all four recognized FAP with high affinity and were rapidly internalized by FAP-positive cells. As a result, the VNAR-Fc constructs were effective antibody-drug conjugates in vitro when attached to an anti-mitotic payload and were able to localize to FAP-positive xenografts in vivo by positron emission tomography. Our findings establish VNAR-Fc constructs as a versatile platform for theranostic development that could yield innovative cancer therapies targeting the TME.