Federated learning (FL) has recently gained considerable attention due to itsability to use decentralised data while preserving privacy. However, it alsoposes additional challenges related to the heterogeneity of the participatingdevices, both in terms of their computational capabilities and contributeddata. Meanwhile, Neural Architecture Search (NAS) has been successfully usedwith centralised datasets, producing state-of-the-art results in constrained(hardware-aware) and unconstrained settings. However, even the most recent worklaying at the intersection of NAS and FL assumes homogeneous computeenvironment with datacenter-grade hardware and does not address the issues ofworking with constrained, heterogeneous devices. As a result, practical usageof NAS in a federated setting remains an open problem that we address in ourwork. We design our system, FedorAS, to discover and train promisingarchitectures when dealing with devices of varying capabilities holding non-IIDdistributed data, and present empirical evidence of its effectiveness acrossdifferent settings. Specifically, we evaluate FedorAS across datasets spanningthree different modalities (vision, speech, text) and show its betterperformance compared to state-of-the-art federated solutions, while maintainingresource efficiency.