Максимилиан родился в 274 году в провинции Нумидия Римской империи в городе Тевест (в настоящее время Тебесса, Алжир, Северная Африка). Поскольку его отец, Фабиус Виктор, был солдатом римской армии, Максимилиан тоже был обязан поступить на военную службу в возрасте 21 года.
Согласно житию, в 295 году, во время царствования императора Диоклетиана, в Тевест проходило очередное заседание комиссии по приему рекрутов на военную службу в императорских войсках. Комиссии состояла из следующих должностных лиц: проконсула Нумидии Кассиуса Диона, прокурора казны податей, императорского чиновника по сбору податей, который в комиссии участвовал как заведующий особым налогом с освобождающихся от воинской повинности (так называемой «податью калек»).
Житие св. Максимилиана недвусмысленно показывает, что он был казнен за отказ от военной службы, которую считал несовместимой с христианской заповедью любить своих врагов, а не убивать их.
- Максимилиан: …Мне непозволительно воевать, потому что я христианин (…) Я не могу воевать, не могу худа делать. Я христианин (…) Я не могу быть солдатом в этом мире, я воин моего Бога.
- Максимилиан: Я не возьму его, этого знака вашей временной власти, и если мне дадут его, я разломаю его, потому что он не имеет никакой цены. Я — христианин, и мне непозволительно носить на шее свинцовый знак, после того как я уже ношу спасительный знак моего Господа Иисуса Христа, Сына Бога Живого. Ты не ведаешь Его, пострадавшего ради нашего спасения, так как Бог отдал Его на страдание за наши грехи. Мы служим Ему, следуем за Ним, Царем жизни, подателем благодати.
- Проконсул (к Максимилиану): Будь же солдатом и возьми знак.
- Максимилиан: Благодарение Господу моему!
- Проконсул: …Так как ты упорно отказываешься нести военную службу, то в пример прочим и получишь заслуженный тобою приговор. (Читает с дощечки) Максимилиан за упрямый отказ от солдатской присяги присуждается к смерти посредством меча.
— «Житие св. Максимилиана» цит. по статье А. В. Пчелинцева. «Право на альтернативную службу»
12 марта 295 года Максимилиан был казнён. Тело его было перенесено матроной Помпеианой в Карфаген и похоронено рядом с мучеником Киприаном.
Мученичество Максимилиана является примером выражения раннехристианских взглядов о несовместимости христианского учения и военной службы, высказанных Оригеном, Тертуллианом, Лактанцием и другими богословами.
Упоминается Римским мартирологом, делающим ошибку в имени. В 1680 году был найден акт его страдания и в 1689 году опубликован бенедиктинским ученым монахом Теодором Руинартом в Оксфорде под наименованием «Акт св. Максимилиана».
День памяти св. муч. Максимилиана Тебесского — 12 марта н. ст.