תנועת הנוער "גורדוניה", שהחלה להתארגן בגליציה המזרחית בשנת 1923, נתגבשה ארגונית בשנת 1925 – שנה בעלת משמעות מיוחדת בתולדות התנועה הציונית, שנת המשבר בתנועה בארץ ובגולה. "גורדוניה", שהיתה תנועה ציונית-סוציאליסטית, לא קפצה מהבלתי נודע לתוך עולם ההויה של הציונות; היא צמחה מתוך המציאות שנוצרה אז בחלק מהתנועה הציונית, בכמה מתנועות הנוער החלוציות.

"גורדוניה" ינקה משלשה מקורות עיקריים: מערכי המוסר של תנועת-נוער, ובעיקר של תנועת-נוער עברית; מתורתו של א.ד. גורדון, תורה לפיה קיים קשר בלתי נפרד בין חיי האדם ועבודתו ובין חיי האומה ואדמתה, וכן, מערכיה העיקריים ועקרונותיה הציוניים-סוציאליסטיים של תנועת "הפועל הצעיר" שבארץ ישראל.

אמנם, כאמור, "גורדוניה" קמה והחלה להתארגן בימי משבר ומצוקה בתנועה הציונית בארץ ובגולה, אך מיסדיה ומארגניה לא נרתעו מהקשיים. הם פעלו בהחלטה נחושה לארגן את "גורדוניה" ברוח עקרונותיה ודרכיו של "הפועל הצעיר" – עם שנויים מסוימים בהתאם לזמן ומקום – ולגבשה כתנועה עממית-חלוצית, שחייבה את חבריה לעלות ארצה. מטרתם היתה ברורה: להמשיך בעליה ארצה בכל האמצעים האפשריים ולעזור לבנות שם את החברה העברית העובדת על ידי הצטרפות למסגרת חיי קבוצה בארץ. ואכן היה שכר לפעולתם: "גורדוניה" התגבשה תוך זמן קצר, התפתחה והתרחבה לכמעט כל ערי גליציה המזרחית והמערבית ומשם גם לארצות אחרות.

"גורדוניה" התארגנה בקראקוב בשנת 1925, בזמן שפעלו בעיר תנועות נוער ציוניות לא מעטות ובכלל זה גם חלוציות. מרבית הנוער העובד והלומד היה מאורגן בתנועות נוער אלה, שהיו אז מאד פופולריות ברחוב היהודי. לאחת מתנועות אלה, תנועת "מרכז הצעירים" (מיסודה של "צעירי ציון" ומעוזה של ה"התאחדות" בעיר), היתה "גורדוניה" מאד קרובה – רעיונית ופוליטית – והיחסים בין שתי התנועות היו הדוקים מאד.

רוב רובם של חברי "גורדוניה" בקראקוב באו משכבות מעוטי היכולת, מנוער מערי ועיירות השדה. לא קלה היתה דרכם של צעירים אלה, שעזבו את מקומות מגוריהם כדי למצוא פרנסה בקראקוב. לא קל היה לגורדונאי הצעיר לקחת חלק בפעולות היום יומיות של הקן לאחר יום עבודה ארוך ומפרך: להשתתף בשיחות על התנועה, עקרונותיה ומגמותיה, ללמוד את השפה העברית, ללמוד כדי להכיר את הארץ ויושביה, את תנאי העבודה ואת החיים היהודיים המתחדשים שם. לא קל היה לו להכין את עצמו גם נפשית, ליציאה לנקודת הכשרה, לניתוק מהמשפחה ולעליה ארצה. אבל עוד יותר קשה היתה דרכו של הגורדונאי המבוגר, שמסיבה כלשהי לא יכול היה לצאת לתקופת הכשרה או לעלות ארצה – אף אם נבע הדבר מסיבה אוביקטיבית, כגון הגבלת העליה שנגזרה על ידי הבריטים. (בעיה זו מצאה את פתרונה החלקי כשהוקמה תנועת-אחות חלוצית בשם "בוסילה", ומבוגרים רבים שהיו חייבים לעזוב את שורות "גורדוניה,, עברו לתנועת "בוסילה".)

שלא בדומה לרוב תנועות נוער החלוציות בקראקוב, שהיו אוטונומיות במובן המוסדי וארגוני ושמרכזם היה בעיר, מרכזה של "גורדוניה" היה בלבוב. בקראקוב היה ל"גורדוניה" מרכז-משנה לגליציה המערבית ושלזיה ובראשו הנהגה חבלית, שהיוותה חלק מההנהגה הראשית שבלבוב. מרכז משנה זה ביצע פעולות רבות בחבלו: עזר בענייני עליה, ארגן (בעזרת מפלגת ה"התאחדות") נקודות הכשרה במקומות שונים בחבל, ערך מפגשים מקומיים וחבליים, ערך פעולות חינוכיות, דאג להקמת מחנות קיץ, עמד בקשר עם המוסדות המרכזיים של תנועות הנוער החלוציות שבקראקוב, כנציג תנועת "גורדוניה" בגליציה, וכן ניהל פעילות ארגונית בעיירות וערי השדה.

למרות הקשיים התפתחה "גורדוניה" קראקוב די יפה. במרוצת הזמן רבים מחבריה עלו ארצה והמשיכו את חייהם בקבוצות ההתישבות של איחוד הקבוצות – וכשאורגנה העליה הבלתי-לגלית ארצה השתתפו בה, באופן פעיל מאד, גם חברי "גורדוניה". עם פרוץ המלחמה תמה אמנם פעולתה הפוריה של "גורדוניה" בקראקוב, אך העבודה לא הופסקה כליל – "גורדוניה" ירדה למחתרת.