مارک رندال پس از بازی در رده‌های پایه برای نورث‌همپتون تاون، در سال ۲۰۰۱ به آکادمی آرسنال پیوست. رندال با قرارداد دانش‌آموزی به آرسنال پیوست و در فصل ۲۰۰۶/۲۰۰۵ هفت بازی در لیگ برتر ذخیره‌ها انجام داد. رندال همچنین تنها بازیکنی در تیم بود که در تمام ۱۸ مسابقه تیم ذخیره‌ها در فصل ۲۰۰۸/۲۰۰۷ به میدان رفت. او در بازی تجلیلی دنیس برکمپ مقابل آژاکس آمستردام در ژوئیه ۲۰۰۶ و همچنین در تور پیش‌فصل باشگاه در اتریش و هلند بازی کرد. او نخستین بازی خود را برای تیم اصلی به عنوان بازیکن تعویضی به جای دنیلسون در مسابقه دور سوم جام اتحادیه آرسنال مقابل وست برومویچ در ۲۴ اکتبر ۲۰۰۶ انجام داد. او همچنین در مسابقه دور چهارم آرسنال مقابل اورتون در ۸ نوامبر ۲۰۰۶ بازی کرد - که باز هم به جای دنیلسون وارد زمین شد - و در مرحله یک‌چهارم نهایی مقابل لیورپول روی نیمکت حضور داشت، اما در آن مسابقه به میدان نرفت.
در ۸ فوریه ۲۰۰۷، او نخستین قرارداد حرفه‌ای خود را با آرسنال امضا کرد و در تابستان ۲۰۰۷ در اردوگاه تمرینی پیش‌فصل سالانه تیم اصلی آرسنال در اتریش شرکت کرد. با این حال، او پس از مصدومیت در نخستین بازی فصل لیگ برتر ذخیره‌ها مقابل فولهام در اواخر اوت، چند ماه اول فصل ۲۰۰۸/۲۰۰۷ را دور از ترکیب بود، اما نخستین حضور ثابت خود در ترکیب اصلی آرسنال را در مرحله یک‌چهارم نهایی جام اتحادیه مقابل بلکبرن در ۱۸ دسامبر ۲۰۰۷ تجربه کرد و همچنین دومین حضور خود در این رقابت‌ها را به عنوان بازیکن تعویضی در دقایق پایانی در دور رفت مرحله نیمه‌نهایی مقابل تاتنهام انجام داد.
رندال در ۳۱ ژانویه ۲۰۰۸، آخرین روز پنجره نقل‌وانتقالات، با قراردادی قرضی به برنلی پیوست و ۱۰ بازی لیگی برای این باشگاه چمپیونشیپی انجام داد. او پس از پایان فصل چمپیونشیپ در ۴ مه به آرسنال بازگشت و در ۱۱ مه در آخرین مسابقه فصل آرسنال مقابل ساندرلند، نخستین بازی خود در لیگ برتر را انجام داد. او در دقیقه ۸۱ به عنوان بازیکن تعویضی وارد زمین شد و گل او در دقایق پایانی مسابقه مردود اعلام شد.
پس از بازی در بخش عمده‌ای از دیدارهای پیش‌فصل ۲۰۰۹/۲۰۰۸ آرسنال، رندال نخستین بازی اروپایی خود را در مرحله سوم انتخابی لیگ قهرمانان اروپا در خانه توئنته در ۱۳ اوت ۲۰۰۸ انجام داد و در دقیقه ۸۴ به عنوان بازیکن تعویضی جایگزین تئو والکات شد. او همچنین ۹۰ دقیقه کامل در پیروزی ۶-۰ آرسنال مقابل شفیلد یونایتد در دور سوم جام اتحادیه در ۲۳ سپتامبر بازی کرد که در آن پاس گل پنجم آرسنال را که توسط جک ویلشر به ثمر رسید داد. او در پیروزی ۳-۰ مقابل ویگان و همچنین در شکست مرحله یک‌چهارم نهایی مقابل برنلی در ترکیب اصلی قرار گرفت. او نخستین بازی خود در مرحله اصلی لیگ قهرمانان اروپا را در ۱۰ دسامبر در شکست ۲-۰ مقابل پورتو با جایگزینی الکساندر سانگ انجام داد.
رندال در پیروزی آرسنال مقابل وست برومویچ در جام اتحادیه پس از تعویض با فرانسیس کوکلن در دقیقه ۵۸ نقش داشت و زمانی که ضربه چیپ او از پشت محوطه جریمه به تیرک دروازه برخورد کرد، به طور غیرمستقیم به کارلوس ولا پاس گل داد. در ۱۵ ژانویه، رندال با قراردادی قرضی تا پایان فصل به میلتون کینز پیوست.
رندال بار دیگر برای فصل ۲۰۱۱/۲۰۱۰ به صورت قرضی اعزام شد؛ این بار به تیمی در لیگ دو یعنی روترهام یونایتد. در پایان دوره قرضی‌اش، او به آرسنال بازگشت و در آنجا قراردادش تمدید نشد که این امر نشان‌دهنده پایان دوران حضور او در آرسنال بود.