Lets say I left one field empty and pressed submit, it highlights the error on the empty field but ajax still submits the form.

How can I stop action and ask for validation?

This is the form markup:

<form id="booking" method="post" class="form" action="" >
    ....some input fields here....
    <button type="submit" id="submit" class="btn btn-large btn-block btn-primary">Book Now</button>
</form>

This is the jQuery Validation:

$('form').validate({
    rules: {
        firstname: {minlength: 2, maxlength: 40, required: true}, 
        lastname: {minlength: 2, maxlength: 40, required: true}, 
        email: {email: true, required: true}, 
        country: {required: true}, 
        mobile: {minlength: 2, maxlength: 40, required: true}, 
        address: {minlength: 3, required: true}
    },
});

This part is the ajax() submit:

$('#booking').on('submit', function(e) {
    e.preventDefault();
    var form = $(this); 
    var post_url = form.attr('action'); 
    var post_data = form.serialize();
    $('#loader', form).html('<img src="http://www.fethiye-tours.com/assets/images/lightbox/loading.gif" /> Please Wait...');
    $.ajax({
        type: 'POST',
        url: 'http://www.fethiye-tours.com/book.php',
        data: post_data,
        success: function(msg) {
            $(form).fadeOut(500, function(){
                form.html(msg).fadeIn();
            });
        }
    });  
});

Quote OP:

"submit works even if the form is not validated"

That's because your custom .on('submit') handler is over-riding the jQuery Validation plugin's built-in submit handler.

Referring to the documentation for the jQuery Validation plugin,

submitHandler (default: native form submit) Type: Function() Callback for handling the actual submit when the form is valid. Gets the form as the only argument. Replaces the default submit. The right place to submit a form via Ajax after it is validated.

In other words, any .ajax() code goes inside of the submitHandler callback function, which only fires when the form is valid. So get rid of your entire .on('submit') handler function and do this instead...

(BTW: properly indented/formatted code is better for everyone to read and troubleshoot)

$(document).ready(function() {

    $('#booking').validate({  // <- attach '.validate()' to your form
        // any rules, options, and callbacks,
        rules: {
            firstname: {
                // minlength: 2,
                // maxlength: 40,
                rangelength: [2,40], // <- combines minlength and maxlength rules
                required: true
            },
            //  more rules,
        },
        submitHandler: function(form) { // <- only fires when form is valid
            $('#loader', $(form)).html('<img src="http://www.fethiye-tours.com/assets/images/lightbox/loading.gif" /> Please Wait...');
            $.ajax({
                type: 'POST',
                url: 'http://www.fethiye-tours.com/book.php',
                data: $(form).serialize(),
                success: function(msg) {
                    $(form).fadeOut(500, function(){
                        $(form).html(msg).fadeIn();
                    });
                }
            });            // <- end '.ajax()'
            return false;  // <- block default form action
        }                  // <- end 'submitHandler' callback
    });                    // <- end '.validate()'

});                        // <- end DOM ready handler

It doesn't look like you need the post_url variable since you're already declaring the url within your .ajax(). Might as well save a line and do the same with post_data too.