בהמשך היישוב השתקם. כשהתארח בו הנוסע אבן בטוטה עדיין מצא אותו בחסות פורמלית של אורדת הזהב. הקהילה המגוונת שחיה בעיר יחד עם יריד העבדים שבה תוארו בשנות ה-1430 על ידי הנוסע הספרדי פרו טאפור.
קאפה הטטרית וקפה העות'מאנית (Kefe).
אחרי המצור על קונסטנטינופול וכיבוש הבירה הביזנטית על ידי העות'מאנים חשיבות קאפה כמרכז מסחרי אירופאי ירדה. זאת בעקבות חסימת מיצרי בוספורוס בפני הסוחרים הנוצרים מן המערב.
בשנת 1454 הופיע בקרבת נמל קאפה צי טורקי שאילץ את ההנהגה הג'נובזית של העיר להסכים לשלם לסולטאן מהמט השני מס שנתי קבוע בשווי 3,000 דוקטים.
מול איום הטטרים של קרים בשנת 1462 כרתו הג'נובזים של קאפה ברית עם מלך פולין קז'ימייז' הרביעי. בתירוץ שהג'נובזים התערבו בענייניה הפנימיים של חאנות קרים, הטורקים העו'תמאנים בפיקוד גדיק אהמט פאשה תקפו את העיר בשנת 1475 וכבשוה, בשיתוף פעולה עם הטטרים של קרים. תושבי רבים של העיר נלקחו בשבי והועברו לאיסטנבול שם נקלטו בתוך שכונת "קפלי מאחאלה", כלומר "שכונת יוצאי קאפה".
תחת הכיבוש העות'מאני הייתה קאפה לבירת סנג'ק ולאחד הנמלים החשובים של האימפריה הטורקית בים השחור. כונתה לפעמים "סטמבול הקטנה" או "הסטמבול של קרים".במאות ה-14–17 שגשג שוב במקום סחר העבדים (הקרויים "יאסיר") וקאפה ארחה את שוק העבדים המרכזי של קרים ואחד משוקי העבדים הגדולים של כל האזור. אלפי העבדים סופקו בעיקר על ידי הטטרים נוגאי שמצפון לים השחור, ששבו אותם בעת פשיטותיהם על אוקראינה, פולין ורוסיה. פרט לסחר העבדים התפתח ענף הפקת מלח בישול מתוך מפרצונים טבעיים. כמו כן הסחר במתכות, בגדים מזרחיים, חרסינה, טבק וקפה.
לעידן הטורקי קשורים טופונימים כמו קוצ'וק יאנישארי (היניצ'ר הקטן) וביוק יאנישארי (היניצ'ר הגדול) - שמות רכסי ההרים המתרוממים דרומית-מערבית מפאודוסיה.
בשנת 1615 תחת הנהגת ההאטמן פטרו קונאשביץ' סהיידצ'ני הרסו הקוזקים מזפוריז'יה את הצי הטורקי וכבשו זמנית את קאפה. בכובשם את העיר, הם שחררו לחופשי את כל העבדים שמצאו בה - רבים מהם רוסים, אוקראינים ופולנים
הקוזקים פשטו שוב על קאפה גם בשנים 1628 (תחת פיקוד ההטמאן מ. דורושנקו) ו-1667 ( לוחמי האוטמאן איוואן סירקו) במטרה לשחרר את העבדים הנוצרים.
בהדרגה העיר איבדה את הילתה המקורית ומספר תושביה התמעט. בשנת 1682 היו בו עדיין 4,000 בתים, מתוכם 3,200 של מוסלמים ו-800 של נוצרים.
פאודוסיה בימי השלטון הרוסי, הסובייטי והאוקראיני.
קאפה חזרה תחת שליטה עות'מאנית עד שנת 1771 כשנכבשה על ידי הצבא הרוסי. ב-1774 סיפוחה לרוסיה קיבל תוקף בהסכם קוצ'וק קאינרג'ה ובשנת 1783 כל חצי האי קרים נפל לידי הרוסים וסופח לאימפריה הרוסית.. בשנת 1787 קאפה שויכה לאזור טוורידה של האימפריה הרוסית וזכתה לבקור המלכותי של הקיסרית הכובשת, יקטרינה הגדולה. במטבעה של קאפה הונפקה מדליה לכבוד ביקורה ביחד עם הקיסר יוזף השני של אוסטריה. חורבות קאפה השאירו אצל יקטרינה רושם רב.
באותה תקופה העיר ירדה בחשיבות, בין השאר, עקב התחרות עם העיר טגנרוג.
בשנת 1796 קאפה הפכה חלק מפלך נובורוסיה ("רוסיה החדשה") וב-1798 הוכרזה לנמל חופשי ל-30 שנה. כעבור 4 שנים, ב-1802 הועברו ליישוב מוסדות מנהליים אזוריים והוא הוכרז לעיר.
בשנת 1804 הוחלט להחזיר לעיר את שמה היווני, הפעם- בגרסתו הרוסית: פאודוסיה.
כשבשנת 1778 החליטו השלטונות הרוסיים להעביר את האוכלוסייה הנוצרית של פאודוסיה לאזור החוף הצפוני של ים אזוב, עשבו את העיר 5,511 ארמנים, 1,648 יוונים ו 24 גאורגים. ההתפתחות הדמוגרפית של העיר במהלך המאה ה-19 תחת השלטון הרוסי הייתה כדלקמן:ב-1829-3,700 תושבים, ב01838 - 4,500, ב-1861 - 8,400, ב-1874 - 10,600 וב-1894 - 17,000.
במאה ה-19 נולד, חי ופעל בפאודוסיה צייר הנופים הימיים איוון אייווזובסקי.
בשנת 1888 ביקר בה הסופר אנטון צ'כוב.
בשנת 1892 הונחו פסי ברזל מג'נקוי ועד פאודוסיה ובשנת 1899 הועבר אליה הנמל המסחרי של סבסטופול, מה שהביא לתנופה כלכלית ועלייה במספר התושבים.
בשנת 1897 מנתה אוכלוסיית העיר 27,328 תושבים (15,995 גברים ו-11,243 נשים) מתוכם - 16,000 רוסים, 3,200 טטרים, 3,000 יהודים, 1,700 קראים, 1,500 ארמנים, ו1,800 מקבוצות אתניות אחרות.
תקופת המהפכה והמלחמה האזרחית 1917-1920.
בימי מלחמת האזרחים שפרצה בעקבות מהפכת אוקטובר פאודוסיה ידעה עם כל האזור רעב, אבטלה, דיכוי, שינויים תכופים של הממשלה. יחידות מפאודוסיה של "הרפובליקה הסובייטית טוורידה" השתתפו באופן פעיל במאבק ה"האדומים" נגד הכוחות האוסטרים-גרמנים, כוחות משלוח אנגלים-צרפתים וצבאות ה"הלבנים".
בסוף חודש אפריל 1918 הגדוד 2 מפאודוסיה ניסה לצאת למתקפת-נגד ולחסום את דרכם של היחידות הגרמניות. בימי הממשל של הגנרל ורנגל פעלה בפאודוסיה יחידה בולשביקית בפיקודו של אי.א. נזוקין. 28 מחבריה נחשפו והוצאו להורג בתחילת 1920.
בנובמבר 1920 בפאודוסיה כונן שלטון סובייטי. אחרי סיום מלחמת האזרחים ותיקיו המקומיים של הצבא האדום, שהשתתפו בקרבות בקרים, התחילו בשיקום הנמל פואדוסיה. בתקופת הרעב באוקראינה וברוסיה הסובייטית תבואה ומוצרי מזון הגיעו לנמל פאודוסיה. במהלך אותה שנה פרקו עובדי הנמל, רעבים ותשושים בעצמם, מעל 90,000 טון של מזון.
משום כך הוועד הפועל המרכזי החליט ב-19 במרץ 1923 להעניק לנמל פאודוסיה את העיטור הגבוה הרפובליקה - עיטור מסדר הדגל האדום של הפדרציה הרוסית הסובייטית. בשנים הראשונות של השלטון הקומוניסטי ירדה אוכלוסיית העיר מ-35,400 תושבים (1921) ל-28,700 (1926). בשנות תוכניות החומש נודעה פאודוסיה בעיקר כמרכז תעשייתי.
ימי מלחמת העולם השנייה.
בימי מלחמת העולם השנייה, גרמניה הנאצית, יחד עם יחידות של בת בריתה, רומניה, כבשה את פאודוסיה בנובמבר 1941. תושביה היהודים של העיר, שהיו 3,248 במספרם לפני הכיבוש הנאצי, נרצחו על ידי איינזצגרופה ד' בין-15 בנובמבר ובין-15 בדצמבר 1941.
ב-26-30 בדצמבר 1941 כוח של 300 נחתים של הצבא האדום בפיקוד הליטננט איידינוב הפתיע את החיילים הרומנים, כבש שוב את העיר. הסובייטים שלטו בה שוב למשך שלושה שבועות בלבד.
ב-18 בינואר 1942 הגרמנים והרומנים חזרו. לראש העיר התמנה חבר המפלגה הקומוניסטית לשעבר, וסילי גרוזינוב.
ב-13 באפריל 1944 העיר שוחררה בעת מתקפה כללית של הצבא האדום. הקרבות היו כבדים והחריבו חלק גדול מן העיר.
העיר קיבלה מהשלטון את עיטור "המלחמה להגנת המולדת" דרגה א.
אחרי שחרור האזור על ידי הצבא האדום ביצע השלטון הסטליניסטי בשנים 1944–1947 את גירוש התושבים הטטרים, הארמנים, היוונים והבולגרים מפאודוסיה ומקרים כולה אל אזורים מרוחקים במרכזה וצפונה של ברית המועצות.
השואה.
אחרי כיבוש קאפה על ידי הצבא הגרמני ב-3 בנובמבר 1941 חברי זונדרקומנדו b10, חלק מהאיינזאצגרופה D, בפיקודו של אוטו אוהלנדורף דרשו מהיהודים המקומיים להירשם. בהמשך ב-
1 בדצמבר 1941 היהודים וקהילת הקרימצ'אקים "הועברה" לתוך "גטו". כעבור 3 ימים, ב-4 בדצמבר 1941 רוב האוכלוסייה היהודית יחד עם קרימצ'אקים, צוענים ואנשים שזוהו כ"קומוניסטים" נרצחו על ידי הזונדרקומנדו, בגיבוי פעיל של ה"שירותים האחוריים" של הארמייה ה-11 שבפיקוד הגנרל אריך פון מנשטיין, במיוחד של המפקדת (אורטסקומדטור) II 915 ושל ז'נדרמריית השדה שבפיקודו של קרל רודולף פאלמן.
מתוך 3,248 יהודים שחיו בפאודוסיה לפני הפלישה הנאצית לברית המועצות, נרצחו עד סוף שנת 1941 כ-2,500-2,000.
לפי הודעת "הלשכה הראשית של ביטחון הרייך" RSHA בין התאריכים 16 בנובמבר ובין 15 בדצמבר 1941 נורו למוות באזור שבאחראיות האיינזצגרופה D - חצי האי קרים כולה - בסך הכל 17,645 יהודים, 2,503 קרימצ'אקים, 824 צוענים ו-212 "קומוניסטים".
במהלך מבצע קרץ'-פאודוסיה העיר נכבשה בחזרה לזמן קצר על ידי הצבא האדום. מציאת קברים המוניים עוררה מעשי נקם נגד חיילים גרמנים שנמצאו במקום ונגד משתפי הפעולה עם הנאצים. לפי מקורות גרמנים של Wehrmacht-Untersuchungsstelle כ-160 מאושפזים במתקן אשפוז ("לאזארט" ראשי) גרמני שבפאודוסיה נרצחו על ידי חמושים סובייטים.
אחרי שהוורמכט כבש שוב את העיר, אנשי צבא סובייטים וניצולים יהודים הואשמו בטבח ונרצחו
מאוחר יותר בצומת הדרכים קרצ'נסקי וסימפרופולסקי בעיר הוקמה מצבה לזכר קרבנות השואה. היא חוללה מספר פעמים על ידי ונדלים, לאחורנה בערב פסח אפריל 2012.
אחרי המלחמה.
בשנים 1990-1948 הוקמה בעיר תשלובת של התעשייה הביטחונית הסובייטית. כאן מוקם הארסנל הגרעיני של צי הים השחור. בעת משבר הטילים בקובה מפאודוסיה יצאו משלוחי נשק לקובה. בפאודוסיה עברו אימונים גם חברי היחידה הראשונה של הקוסמונאוטים הסובייטים, לקראת המשימות בחלל.
57 % מהתושבים הכשירים לעבוד הועסקו במפעלים ובבסיסים הצבאיים.
שוקמו גם חלק מן המפעלים האזרחיים של פאודוסיה כמו בית החרושת לסיגריות וטרמינל הנפט (שהוקם ב-1938) ונבנו מפעלים חדשים כמו המספנות "מורה" ו"סודוקומפוזיט", מפעלים למתקנים גרעיניים (1946), למכונות (1952), לאופטיקה, יקבים. במאה ה-21 התעשייה הצבאית נקלעה למשבר קשה והושבתה במידה רבה.
בשנת 1954 יחד עם כל חצי האי קרים הועברה העיר על ידי ניקיטה חרושצ'וב מהפדרציה הרוסית לרפובליקה הסובייטית הסוציאליסטית האוקראינית, כמחווה לעם האוקראיני. המהלך נראה אז סימבולי בלבד, מפני שאוקראינה הייתה גם היא חלק מברית המועצות. בשנת 1991 חצי האי קרים הפך חלק מאוקראינה העצמאית, החל משנת 1992 במסגרת הרפובליקה האוטונומית של קרים.