A message indicating a route to a network destination is received at a routing service from a particular routing device of a provider network. The message is formatted in accordance with a set of APIs implemented using a stateless protocol, and indicates a route to a particular network destination associated with a particular RIB stored at a persistent data store accessible from various nodes of the routing service. The RIB is modified accordingly. A routing service back-end node generates an entry of a forwarding information base (FIB) associated with the particular RIB. The FIB entry is transmitted to one or more routing devices including the particular routing device, and is used to forward data packets of one or more other services.