На Востоке ситуация была иной. Послание было хорошо известно в Александрии (его признавали апостольским Пантен, Климент Александрийский, Ориген). В папирусе начала III в. оно помещается среди Посланий Павла сразу после Послания к Римлянам и до первого Послания к Коринфянам (в сирийском Каталоге из монастыря великомученицы Екатерины (около 400 г.) Послание Евреям находится между Посланием к Римлянам и Посланием к Колоссянам). 39-е праздничное Послание Афанасия (367 г.) включает Послание Евреям в число Посланий Павла между вторым Посланием к Фессалоникийцам и первым Посланием к Тимофею (то же самое в 60-м правиле Лаодикийского (около 343 г.), в Синайском и Александрийском кодексах, в Пешитте). В Ватиканском кодексе оно также помещено после второго Послания к Фессалоникийцам, однако Пастырские Послания в нём отсутствуют. По мнению исследователей, 14 Павловых Посланий, включая в их число Послание Евреям, упоминают в сочинениях святители Кирилл Иерусалимский, Григорий Богослов, Амфилохий Иконийский; то же в 85-м Апостольском правиле (около 380 г.). Только Епифаний Кипрский причисляет к каноническим 13 Павловых Посланий. Из латинских писателей IV в. Послание Евреям, в первую очередь, признают те, кто были тесно связаны с Востоком, – Иларий Пиктавийский, Иероним Стридонский, Руфин. Гиппонский собор (393 г.) и 39-е правило третьего Карфагенского собора (397 г.) называют Послание Евреям среди канонических книг, но отдельно от Посланий Павла. Только шестой Карфагенский собор (419 г.) включает его в число Павловых. Августин Блаженный мотивировал внесение Послания Евреям в собрание канонических книг тем авторитетом, которым это Послание пользовалось на Востоке. Как полагают исследователи, дольше всего признанию Послания Евреям сопротивлялась Римская церковь. Только Декрет папы Геласия (VI в.) включил его в число канонических. В связи с решением вопроса о каноничности Послания Евреям в древней церкви был поставлен вопрос об авторстве Послания Евреям. Климент Римский, чьё первое Послание к Коринфянам является одним из ранних свидетельств о существовании Послания Евреям, нигде не называет его автора (однако это, по мнению исследователей, не может служить аргументом в пользу анонимности Послания, поскольку Климент вообще упоминает апостола Павла как автора только первого Послания к Коринфянам). По свидетельству Евсевия Кесарийского, самое раннее прямое указание на авторство апостола Павла приводит Климент Александрийский, который, как полагают исследователи, основывался на мнении своего учителя Пантена. В произведениях Климента Послание также атрибутируется апостолу Павлу. Однако Ориген отмечал, что стиль Послания Евреям резко контрастирует с другими Посланиями Павла, допуская, что его написал один из учеников, слушавших благовестие апостола: «В языке Послания, озаглавленного «К Евреям», нет особенностей, свойственных языку апостола, который признаёт, что он «неискусен в слове», то есть в умении выражать свои мысли. Послание составлено на хорошем греческом языке, и каждый, способный судить о разнице стилей, это признаёт. Мысли же в этом Послании удивительные, не уступающие тем, которые есть в Посланиях, признаваемых подлинно Павловыми. Что это так, с этим согласится каждый, кто внимательно читает эти Послания... Если бы мне пришлось открыто высказаться, я бы сказал: мысли в этом Послании принадлежат апостолу, а выбор слов и склад речи – человеку, который вспоминает сказанное апостолом и пишет, как бы поясняя сказанное учителем. Если какая-нибудь Церковь принимает это Послание за Павлово, хвала ей за это. Не зря же древние мужи считали это Послание Павловым. Кто был настоящий его автор, ведомо только Богу. Ещё до нас его приписывали одни Клименту, епископу Римскому, другие – Луке, написавшему Евангелие и Деяния».