Был сформирован в 70 году Веспасианом взамен XVI Галльского легиона. По всей видимости, он сразу был отправлен в Каппадокию. Принимал участие в римско-парфянских войнах. Позднее легион был переведён в Сирию.
Последние упоминания о легионе относятся к началу V века. Эмблемой XVI Стойкого Флавиева легион в более ранних исследованиях считали льва[1]. Позже было выяснено, что это Пегас[2].
Бывший XVI Галльский легион, который был опозорен своим поведением во время Батавского восстания (69—70 годы), был воссоздан императором Веспасианом под названием XVI Стойкий Флавиев и отправлен в восточные провинции[3]. Эта передислокация была своего рода наказанием, потому что солдаты XVI Галльского легиона происходили из Галлии на западе. Тем не менее, легионеры, должно быть, были рады, что они обошлись относительно мягким наказанием и не были с позором исключены из состава римской армии[4].
Веспасиан реорганизовал границу вдоль Евфрата (например, была присоединена Мелитена) и новый легион в течение некоторого времени размещался в Сатале на верхнем Евфрате на северо-востоке Каппадокии. Он оборонял этот участок, граничившей с Арменией, вместе с XII Молниеносным легионом. Об этом периоде истории легиона известно мало подробностей[4]. В 75 году вексилляции XVI Стойкого Флавиева, IV Скифского, III Галльского и VI Железного легионов были привлечены к строительству канала и моста в Антиохии[5][6].
XVI Стойкий Флавиев легион принимал участие в парфянском походе Траяна в 114—117 годах[3]. Преемник Траяна Адриан заменил XVI Стойкий Флавиев легион в Сатале на XV Аполлонов легион и отправил его в Самосату на Евфрате[7]. Это был мирный период для легиона, так что не удивительно, что были обнаружены доказательства гражданской деятельности легиона, например, строительство туннеля возле Селевкии Пиерии[4]. Вексилляция легиона отправлялась на подавление восстания Бар-Кохбы в Иудее в 132—135 годах[8].
Одна из надписей времён правления Антонина Пия называет его «Flavia Fidelis» (рус. Флавиев Верный)[9]. Из другой надписи, относящейся к тому же периоду, известно, что вексилляция легиона располагалась возле Селевкии Пиерии[10]. XVI Стойкий Флавиев легион принимал участие в кампании императора Луция Вера против парфян, предпринятой в качестве ответной меры на разгром римской армии в Армении. В результате была завоевана Месопотамия. Таким образом, впервые за полвека легион использовался в крупномасштабном походе[4].