ভিক্টোরিয়া পার্ক ইংল্যান্ডের রানী ভিক্টোরিয়ার নামে প্রতিষ্ঠিত। উনিশ শতকের প্রথমার্ধে নওয়াব স্যার আবদুল গনির উদ্যোগে ঢাকার সদরঘাট এলাকায় ‘আন্টাঘর’ নামের একটি আর্মেনীয় ক্লাবঘরের ধ্বংসাবশেষের ওপর পার্কটি তৈরি হয়। সে সময় ওই ক্লাবের পাশের এলাকায় অনেক আর্মেনীয় বসবাস করত। ১৮৫৭ সালের সিপাহি বিদ্রোহের সময় ভিক্টোরিয়া পার্ক বিশেষ পরিচিতি অর্জন করে। এখানে একজন মহিলাসহ কয়েকজন বিদ্রোহীকে ফাঁসি দেওয়া হয়। ১৮৫৮ সালে ঢাকার বিভাগীয় কমিশনার বিপুলসংখ্যক মানুষের এক সমাবেশে রানী ভিক্টোরিয়ার বিখ্যাত ঘোষণা পাঠ করেন। ডিম্বাকৃতির এ পার্কটি ছিল লোহার রেলিং ঘেরা। আর্মেনীয় ক্লাবঘরের চার কোনায় বসানো সীমানা নির্দেশক চারটি ব্রিটিশ কামান পরবর্তীকালে তুলে এনে পার্কের ভিতরে বসানো হয়। টেলরের সময় এ পার্কের পাশের এলাকা এক ভিন্নরূপ ধারণ করে। পুরান ঢাকার ব্যস্ত সড়কগুলোর সংযোগ-মোড়ে পার্কের চার কোনা আকৃতির ছোট একখ- খোলা জায়গার মাঝখানে গোলাকৃতি বাগান তৈরি করা হয়। সংলগ্ন এলাকা ও আধামাইল দূরত্বে নদীতীর বরাবর অবস্থিত ছিল ইংলিশ ফ্যাক্টরি, সেন্ট টমাস চার্চ, সরকারি কলেজিয়েট স্কুল, মিটফোর্ড হাসপাতাল ও অধিকাংশের ইউরোপীয়র বসতবাড়ি। সিপাহি বিদ্রোহের পর দীর্ঘকাল পর্যন্ত পার্কটি ছিল জনহীন। দিনের বেলায়ও এখানে লোকজন আসতে ভয় পেত।
স্বাধীনতার জন্য জীবন উৎসর্গকারী দেশপ্রেমিকদের অমর স্মৃতি রক্ষার্থে ১৯৫৭ সালে এ পার্কে এক বিশাল চার কোনা স্মৃতিস্তম্ভ নির্মাণ করা হয়। সিপাহি বিদ্রোহ হয়েছিল ইংরেজ রাজত্বের অবসান ঘটিয়ে মুঘল সম্রাট বাহাদুর শাহকে পুনঃস্থাপিত করার জন্য। তাই তাঁর স্মরণে পার্কের পুনর্নামকরণ হয় বাহাদুর শাহ পার্ক। পার্কের ভিতরে এ চার কোনা স্মৃতিস্তম্ভটি এখনো দাঁড়িয়ে আছে।