원래 크림 반도는 고대 시대에 그리스 인들의 식민도시가 존재하고 있었으며 이곳에 스키타이가 이동해왔다. 그리고 스키타이 인들은 사르마트 인들에게 패배하기까지 상당히 오랜 기간 동안 크림 반도를 지배했다. 이 지역에는 또한 카프카스 계 민족들이 거주하고 있었으나 9세기부터 하자르나 페체네그, 킵차크-쿠만 인 등 투르크계 유목민들이 흘러 들어와 살고 있었다. 이들은 몽골-타타르 인들이 모스크바 공국을 침략하기 오래 전부터 우크라이나 초원 지대의 진출을 노리고 있었으며 키예프 공국과 오랜 시간을 두고 대립하던 사이였다. 그래서 킵차크 칸국이 건국되기 전에도 이 유목민족들을 타타르 인으로 통칭하여 불러 오기도 했다. 그리스 인, 투르크계 알란 인과 기타 페르시아-아리안계 민족, 체르케스 인과 카프카스의 원주민 같은 여러 민족들이 크림 반도에 정착한 기타 투르크계 종족인 훈족, 하자르 족, 페체네그 족, 킵차크-쿠만 족 등 수많은 민족들이 혼혈하여 크림 타타르 인을 탄생시킨 것으로 보인다. 이들 수많은 종족들 중에서도 가장 큰 역할을 했던 종족은 킵차크-쿠만 인으로 알려진 폴로베츠 인이다. 11~12세기 폴로베츠 인은 볼가 강, 아조프 해, 흑해 연안의 초원 지대에 거주하기 시작했고, 점차 크림 반도로 침투하기 시작했다. 

게다가 1241년 몽골-타타르 인이 러시아 남부에 침입하여 약탈하자, 폴로베츠 인과 키예프 공국은 서로 연합군을 형성했다. 그러나 이들 연합군들은 몽골군에 패했으며 당시 흑해 연안 북부의 폴로베츠 인 공동체도 몽골-타타르 인들의 공격으로 완전히 붕괴되었다. 이에 이들 폴로베츠 인들은 크림 반도의 여러 도시들을 건설하고 철저히 은닉하면서 기회를 노렸던 것으로 보인다. 1244년 크림 반도 역시 바투가 이끄는 몽골군에 함락되어, 크림 반도의 초원지대는 킵차크 칸국의 구성원으로 존재하게 되었다. 이 시기 크림 반도에는 시린(Sirin), 아르긴(Argin), 바린(Barin) 등과 같은 타타르계 가문이 등장했으며, 이들은 후일 크림 타타르 귀족 계급의 중심이 되었다. 이 무렵부터 타타르라는 명칭이 본격적으로 나타나게 되었으며, 이는 몽골군에 의해 세워진 국가에 거주하는 모든 투크르계 민족을 통칭 및 지칭하는 명칭으로 변하게 되었다. 이러한 배경에서 건국된 크림 칸국(Crimean Khanate)은 1430년, 킵차크 칸국의 시조인 바투의 동생으로 알려진 샤이반(Шибан)의 후손인 하츠 게레이(Hacı Geray)가 세운 국가로 바투의 부친인 칭기즈칸의 장남 주치의 왕비이자 바투와 샤이반의 모친인 울리치 게레이(Ulitsy Gearey)가 케레이트 옹칸의 누이인 바르볼트 케레이(Barbolt Gearey)의 후예로 알려져 있으며 주치의 결혼이 보르지긴 왕가와 케레이트 가문의 융합을 의미하기도 한다. 

한편 1433년 킵차크 칸국의 수도인 사라이에서 궁정 반란이 일어났다. 그와 더불어 당시 킵차크 칸국의 칸이었던 울루 무함마드(Ulugh Muhammad)는 칸의 자리에서 추방되어 아들 무스타파(Mustafa)와 함께 도주하게 되었고 이들 부자는 볼가 강을 따라 올라가 킵차크 칸국의 국경을 넘게 되었다. 하지만 이들 부자들은 새로운 칸인 셰이드 아흐마드(Syed Ahmed)에게 굴복할 생각은 전혀 없었고 볼가 강 상류와 카마 강이 만나는 카잔으로 도주하여 카잔에서 칸을 칭하면서 카잔 칸국을 세웠다. 카잔 칸국의 주민들은 지배층인 몽골-타타르족과 볼가 불가르 인들의 후예인 추바시 인, 핀-우그르 계의 모르도바 인, 투르크계의 바시키르 인 등으로 구성되어있었다. 울루 무함마드는 카잔 지역을 9년간 통치하며 모스크바를 자주 공략하여 약탈하였고 이 외에도 멀리 노브고로드까지 원정을 자주 다니곤 했다. 하지만 그는 또 다시 궁정 내부에서 반란이 발생하는 사태를 겪게 되었다. 반란을 일으킨 자는 아들인 무스타파였고 울루 무함마드는 아들에게 피살되었다. 이러한 내부 쿠데타로 인하여 무스타파의 동생 카심은 모스크바 공국으로 도주하게 된다. 이는 울루 무함마드가 막내아들인 카심을 총애했고 그를 다음 후계자로 낙점하고 있었다.

그러한 상황에서 무스타파는 부친과 카심에 대한 불만이 팽배했고 이는 무스타파가 노브고로드로 원정을 떠났을 때 촉발되었다. 무스타파는 동생인 카심을 처단하려 하였으나 카심은 이미 모스크바로 도주한 상태였다. 무스타파는 카잔 칸국의 칸이 되면서 모스크바 공국 내에서 벌어진 내전에 관여했고 바실리 2세를 반란을 일으킨 세력들에게 포로로 잡혀 눈을 뽑아 장님으로 만들어버리는데 일조를 했다. 하지만 이 내전은 카심이 장님이 된 바실리 2세를 도와 카잔 칸국의 군대를 축출하고 반란 세력들을 모두 처형하면서 바실리 측의 승리로 끝나게 된다. 이 때 바실리 2세를 도운 공으로 카심은 그의 이름을 딴 카시모프라는 도시를 영지로 받고 카시모프 칸국, 혹은 카심 칸국이라는 일종의 모스크바 공국의 인정을 받고 슬라브 인들의 조종을 받는 국가를 건국하게 된다. 15세기 전반기 킵차크 칸국이 대거 붕괴되면서 크림 지역에는 독립적인 움직임이 일어나기 시작했는데 하츠 게레이(Hacı Geray)는 평소 킵차크 칸국에 불만을 가진 투르크 세력들을 규합하여 각 도시에 있던 킵차크 관리들을 축출하기 시작했다. 이러한 크림 지역의 킵차크 관리들과 총독들은 1244년부터 1449년까지 존재했다. 그러나 1449년 크림 반도의 남쪽 연안과 인근 지역에서 킵차크 총독에 대한 반란이 발생하면서 수도인 사라이와 멀리 떨어져 있는 곳에 위치함으로 인하여 크림 킵차크 총독은 정부에게 별도의 허락을 받지 않고 군을 증강할 수 있었지만 반란이 발생하자 군대가 킵차크 총독에 모이지 않았다. 

그러자 킵차크 총독은 크림 반도 남쪽 연안을 반란 세력에게 내줄 수밖에 없었다. 마침 하츠 게레이가 크림 반도 서부 지역을 함락시키면서, 크림 반도 남쪽 연안의 반란군과 합세했다. 그리고 킵차크 정부군이 합류하기 전에 킵차크 총독과 몽골-타타르 세력을 축출하려 하였다. 하츠 게레이는 사라이와 지리적으로 멀다는 이점을 가지고 킵차크 총독의 군대를 드네프르 일대로 추방했고 하츠 게레이는 크림 반도 남쪽 연안의 세바스토폴에서 크림 칸국을 세웠다. 그러나 나라는 세웠지만 하츠 게레이가 칸이 되는 것은 쉽지 않았다. 특히 킵차크 칸국의 쿠축 무함마드(Küchük Muhammad, 1435~1459)의 반발이 가장 심했는데 1449년에 독립한 크림 칸국을 인정하지 않았다.  더구나 킵차크 칸국의 세력이 약해졌어도 드네프르 강 유역의 각 도시 군들은 여전히 킵차크 칸국에게 조공을 바치는 봉신국(封臣國)이었고 이들은 새로 건국된 크림 칸국을 자주 공격했다. 그러한 상황으로 인하여 하츠 게레이는 제대로 된 칸으로 인정받고 안정적으로 즉위하기 위하여 가장 먼저 폴란드-리투아니아 공국과 동맹을 맺었다. 그리고 이어 모스크바 대공국을 상대로 동맹을 맺었으며 이들 드네프르 강 유역의 소(小) 공국들에 반격까지 가해 드네프르 중류 지역까지 점령하기도 했다. 

하지만 킵차크 칸국의 군사들이 돈 강을 건너 드네프르 지역의 크림 군을 공격했고 이후에는 크림 반도의 길목인 헤르손(Херсон)이 포위되는 지경에 이르렀다. 이에 하츠 게레이는 결국 포로들을 풀어주는 조건으로 강화해야했다. 얼마 후 킵차크 칸국의 세력이 다시 강대해지고 모스크바의 세력 또한 드네프르 일대로 확장하는 움직임이 포착되자 폴란드-리투아니아는 하츠 게레이를 구원하기 위해 블라디스와프 브레스트 대공이 4만의 정예병을 파견하게 되었다. 이로 인하여 전쟁은 폴란드-리투아니아가 개입한 국제전이 되었고 하츠 게레이는 폴란드-리투아니아의 지원을 받아 드네프르 지역의 킵차크 군을 공격했다. 폴란드-리투아니아 군과 함께 킵차크 군의 본영인 자포리제(Запоріжжя)를 공격하여 점령하였다. 킵차크 군은 패배하여 사라이로 퇴각했고 하츠 게레이는 자포리제에서 폴란드-리투아니아 군의 호위를 받으며 칸으로 등극했다. 이렇게 폴란드-리투아니아의 승인을 받아 칸이 된 하츠 게레이는 모스크바에 사신을 보내 자신의 즉위를 알리고 함께 킵차크 칸국을 공격할 것을 요청했다. 모스크바는 당연히 이 요청을 받아들여 군사들을 보내왔고 돈 강 평원 전투에서 모스크바-폴란드-크림의 연합군은 킵차크의 군대를 격파하면서 돈 강에서 완전히 축출했다. 

이후 1450년 킵차크 칸국은 크림 지역에 약 10만 대군을 파견했지만 하츠 게레이는 배후의 카프카스 아르메니아 왕국, 오스만투르크와 동맹을 맺고 킵차크 칸국을 고립시켰다. 킵차크 칸국의 10만 군대는 오늘날 크림 서쪽 케르치(Керчь)에서 하츠 게레이의 크림 칸국의 7만 군대에 의해 케르치 해협을 도하하는 도중 상당수 수장되는 패배를 당했다. 당시 이들 중 2만의 몽골-타타르 군이 포로로 잡혀 세바스토폴로 압송되기도 했는데 이들 대부분은 크림 지역에 거주하던 투르크계 귀족들의 노예가 되었다. 킵차크 칸국을 토벌한 하츠 게레이는 흑해를 사이로 점차 상인들을 가장해 세력을 확장해오는 제노바 인들에 위협을 느끼게 된다. 그러한 제노바 인들은 드네프르 강 하구와 돈 강 하구, 그리고 카프카스의 서해안에 상업적 거점을 확보하고 킵차크 칸국 및 모스크바와 교역을 하려고 했다. 그러려면 제노바까지 연결하는 항로에 거점을 둘 수 있는 지역을 물색하게 된다. 처음에는 드네프르 강 하구 지역을 항구로 사용하고자 했지만 지형적 특성상 항구를 건설하기에는 많은 어려움이 동반되는 곳이었다. 그래서 기항지로 찾은 곳이 크림 칸국의 수도인 세바스토폴이었다. 제노바 인들의 해군은 막강했고 해상 세력에서 베네치아와 사보이, 나폴리와 함께 지중해 지역의 해상 상권을 장악하던 도시 국가였다. 

하츠 게레이는 세바스토폴 인근까지 접근하려는 제노바 상인들을 모두 붙잡아 제노바로 돌려보냈다. 그러나 제노바 또한 해상 군사적 요충지인 세바스토폴을 포기하지 않았다. 제노바는 해군 8만에 400척의 대 선단을 동원하여 크림 반도를 공격하기 위해 보스포루스 해협을 통과했다. 당시 크림 칸국은 제대로 된 해군과 함대가 없었다. 그러한 열세를 극복하기 위해 하츠 게레이는 1455년 오스만투르크에 사절을 파견했다. 이미 보스포루스 해협을 통과한 제노바의 퇴로를 차단하기 위해 오스만투르크가 필요했고 하츠 게레이와 크림 군은 세바스토톨의 수성을 위해 상륙전을 봉쇄하기 위해 해변 가에 상당히 많은 양의 포대를 구축했다. 오스만투르크 또한 지중해 해안을 돌아다니는 제노바가 위협적이었고 게다가 콘스탄티노플을 함락시킨지 불과 2~3년 밖에 되지 않아 보스포루스 해협 인근 지역이 매우 불안한 상태였다. 오스만투르크는 1456년 보스포루스 해협에 대 선단을 파견하여 유라시아로 연결되는 대륙을 봉쇄했다. 결국 남은 것은 제노바의 함선 400척과 상륙군을 포함한 8만의 대군이었다. 따라서 하츠 게레이는 1차 저지선의 포대로 나가 군을 지휘하게 된다.이러한 일련의 상황에서 하츠 게레이는 오스만투르크가 더 이상 개입하지 않을 것으로 생각하고 우선 방어전에 나설 수밖에 없었다.

 제노바 해군은 그 해 7월, 세바스토폴 바다 위에서 나타났고 이어 상륙을 시도했다. 이에 1선의 크림 군은 화포로 응사하여 제노바 군의 상륙을 철저히 방해했다. 이에 제노바는 대규모 함선들을  해안으로 접근시켜 화포로 근접전을 벌였다. 문제는 크림 칸국의 군대가 해안 방어전에 대한 경험이 전무 하다는 것이었다. 함선이 접안할 때까지 1선의 크림 군이 한 방어 행위는 화포를 쏘아 접근을 방해하는 것 외에는 없었다. 이러한 약점을 간파한 제노바 군은 함대에서 닺을 내리고 함대의 접안을 시도했으며 포탄 속을 뚫고 상륙에 성공했다. 이어 1선에서 크림 군과 강력한 해병대를 앞세운 제노바 군과 백병전이 벌어졌다. 중앙군이 백병전을 벌이는 사이 좌, 우익의 제노바 해군이 상륙에 성공했고 1선에 방어 군에 대한 포위, 섬멸전을 전개했다. 이에 하츠 게레이는 성 안으로 철수하여 수성 전을 벌이는 전략을 선택했다. 1선의 크림 군의 포대와 진지는 대거 파괴되고 대신 제노바 군의 포대가 들어섰으며 수많은 크림 군이 살해되거나 포로가 되었다. 이로써 1선 제노바 군의 상륙을 저지하는 전략은 실패했고 두 번째 전략인 수성 전에 나서게 되었다. 크림 칸국 세바스토폴 주민들과 크림 군은 이러한 상황에 맞서 4주 동안 공성전에 맞서 항쟁을 벌였다. 투석기와 화포를 앞세운 제노바 군은 서전의 승리로 기세가 올라 성을 공략했다. 

그러나 제노바 군은 크림의 수성 전략으로 인하여 성 내 진입에 계속 실패했다. 하츠 게레이는 수성 전을 전개함과 동시에 모스크바에 구원을 요청했다. 모스크바 입장에서는 크림 칸국이 제노바에게 붕괴되면 드네프르를 따라 키예프에 도달할 것이고 키예프 공후들의 안전을 장담할 수 없다는 불안감을 가지고 있었기 때문에 출정을 결행했다. 우선 페레야슬라블과 체르니코프의 군대가 출정했고 이어 트베리 군과 모스크바 군이 볼가 강의 수로를 이용하여 남하하여 크림 동쪽 케르치 해안에 도착했다. 페레야슬라블과 체르니코프의 군대는 헤르손에 도착하여 대공은 바실리 2세(Василий II)의 명을 기다리게 된다. 바실리 2세의 도하가 허락되고 페레야슬라블과 체르니코프의 군대가 들어서면서 제노바 군은 완전히 포위되었고 이어 바실리 2세의 군대가 세바스토폴 동쪽에 진입하자 중앙의 하츠 게레이의 크림 군이 성 밖으로 나와 제노바 군과 격전을 벌였다. 이미 전의를 상실한 제노바 군은 거의 대부분 궤멸되었고 제노바의 함대는 대부분 파쇄 되거나 크림 군과 러시아 군에게 노획되었다. 이로써 살아 돌아간 제노바 함대는 50여 척에 불과했으나 보스포루스를 봉쇄하고 있던 오스만투르크 군에게 모두 전몰되었다. 이로써 제노바는 함대를 모두 잃고 지중해에서 그 세력이 급격히 약화되었으며 크림 칸국은 러시아와 오스만투르크의 도움으로 인하여 본격적인 독립 국가로써 성장하게 되었다.