구 21번이 전신이다. 김해시와 김해군이 통합하기 전에는 농어촌버스였으며 '시외버스터미널 - 가락로 - 삼계 - 상동 - 봉암' 구간을 1일 4회 운행했다.

1995년 11월 20일에 김해시와 김해군이 통합하게 되어 '어방동 - 삼방동 - 초선대 - 김해시청 - 가락로 - 외동 - 내동 - 상동 - 봉암 - 매리 - 여차' 구간을 1일 5회 운행하게 되었다.

1998년 6월 27일 개편 당시에는 '어방동 - 지내동 - 삼방동 - 인제대 - 복음병원 - 가락로 - 공병학교 - 상동 - 봉암/매리·여차' 구간을 1일 5회 운행했다. 그런데 당시 기사에서 봉암 4회, 매리·여차 2회라고 되어 있는데 1일 5회라고 하니 맞지 않는다. 아마 봉암 4회 중 1회가 여차에서 출발하고 나머지 3회는 봉암에서 종착하며 나머지 매리·여차 경유 1회는 봉암을 경유하지 않았다면 말이 된다.

2000년 4월 29일에 '외동터미널 - 분성로 - 삼방동 - 인제대 - 복음병원 - 가락로 - 구산백조아파트 - 상동 - 봉암/여차'로 노선이 조정되었으며 1일 7회 운행하게 되었다. 봉암 4회, 여차 2회인 것은 변함이 없었다.

2001년 12월 개편 때 번호가 71번으로 바뀌었고 '외동터미널 - 김해중부경찰서 - 농협김해시지부 - 구산백조아파트 - 삼계정수장 - 나전 - 우계 - 상동면사무소 - 봉암' 구간을 운행하게 되었다.

2000년 12월 21일에 여차·감로 공영버스가 신설되어 여차 일대의 구간을 넘겨줬다. 다만 외동행 첫차에 한해 매리 출발로 운행하였다.

2007년 9월 1일부터 일부 시간대에는 상동면 봉암에서 매리까지 연장운행한다.

2011년 9월 9일부터 4번에서 운행하던 저상버스 2대를 가져왔고 기존 본선인 A노선과 매리로 가는 B노선으로 나누어 교대로 배차하였다. 그러나 노선 번호는 그대로 71번 하나로 유지하다보니 이용자들의 불편이 가중되었다.

때문에 2012년 이후로 A노선은 71번으로 B노선은 72번으로 분리되었다.

2015년 6월 5일에 71번은 72번에게 흡수 통합 되었다.

그러나 봉암 출발이었던 71번을 흡수통합하는 과정에서 아무 보상책도 없이 봉암마을을 그냥 지나치다 보니 마을주민들의 불편이 생겼는지[6] 72번이 하루 6회 봉암마을 경유 노선으로 노선이 살짝 수정되었다.

전 차량 저상버스가 사용되었었다.

파일:부산김해선상징1.png 부산김해경전철: 봉황역, 장신대역, 가야대역