Впервые Гомельский мытный прикаморок Глусской мытной каморы Белорусского таможенного округа упоминается в рукописях 1766 года.
Находясь на лесных дорогах и границах княжеств, древнебелорусские мытники боролись с «промытчиками» — контрабандистами, норовившими незаконно провести товары и не платить мыто (пошлину). В дикой глуши дремучих лесов это было очень опасное занятие, поэтому им в сборе мыта нередко помогали вооружённые отряды княжеских дружинников.
История таможенного дела в Гомельской области берёт начало с февраля 1983 года. В связи с решением советского правительства о строительстве в городе Жлобине Белорусского металлургического завода иностранными подрядчиками, с ввозом материалов и оборудования из-за рубежа возникла необходимость в создании подразделения таможни.
Для обеспечения таможенных операций Главным управлением Государственного таможенного контроля при Совете Министров СССР был учреждён Жлобинский таможенный пост — первый внутренний таможенный пост в зоне деятельности Белорусской территориальной таможни ГУ ГТК СССР.
14 марта 1991 года был создан Гомельский таможенный пост Минской таможни со штатной численностью 3 единицы.
С 4 мая 1993 года Гомельский таможенный пост Минской региональной таможни преобразован в Гомельскую таможню со штатной численностью 156 человек. В её структуру вошли ранее действующие на территории области Жлобинский (создан в августе 1982 г.), Гомельский (март 1991 г.) и Светлогорский (октябрь 1992 г.) таможенные посты (далее — ТП) Минской региональной таможни и вновь созданные таможенные посты: «Гомель-пассажирский», «Селище-1», Круговецкий, Кравцовский, Комаринский. Впоследствии создан ТП «Полесье» (ноябрь 1993 г.), Речицкий и Добрушский ТП (март 1994 г.), ТП «Гомель-грузовой» (июнь 1994 г.).
Первым начальником Гомельской таможни в 1993 году был назначен Валерий Шевелев.
С 1 июля 1993 года на участок границы области с Россией и Украиной заступили первые смены гомельских таможенников; они контролировали 415 километров таможенной границы, в том числе с Украиной — 235 км, из которых 137 километров границы проходили по руслу рек.
В июле 1995 года в соответствии с межправительственным соглашением между Беларусью и Россией прекратили свою работу таможенные переходы «Перелёвка» и Добрушский на границе с Россией.
В 1998 году начальником таможни был назначен Василий Гнатюк.
С апреля 2000 года таможне предоставлено право осуществлять оперативно-розыскную деятельность.
15 ноября 2001 года введён в эксплуатацию первый пусковой комплекс, а 13 декабря 2002 года состоялось торжественное открытие всего пограничного пункта пропуска «Новая Гута». Строительство его велось с декабря 1997 года.
В соответствии с Указом Президента Республики Беларусь №470 должностные лица таможни впервые приняли присягу на верность Республике Беларусь и её народу.
С 2005 учебного года по инициативе руководства таможни и при поддержке Гомельского облисполкома в учреждении образования «Белорусский государственный университет транспорта» открыта специальность «Таможенное дело».
С 18 ноября 2008 года начальником Гомельской таможни назначен Олег Борцов.
Приказом Государственного таможенного комитета Республики Беларусь 3 октября Гомельская таможня реорганизована путём присоединения к ней Мозырской таможни.
С 17 апреля 2012 года Гомельской таможней руководит Феликс Яшков.
С 1 мая 2013 года должностные лица таможни приступили к оперативному управлению государственными контрольными органами, осуществляющими транспортный, ветеринарный, фитосанитарный и санитарно-карантинный контроль, с 1 января 2014 года начали осуществлять функции автомобильного и документарного санитарно-карантинного контроля.
