I have declared post type as below:

 $args = array(
        'labels' => $labels,
        'public' => true,
        'publicly_queryable' => true,
        'show_ui' => true,
        'show_in_menu' => true,
        'query_var' => true,
        'rewrite' => array('slug' => 'agences'),
        'capability_type' => 'post',
        'has_archive' => true,
        'hierarchical' => false,
        'menu_position' => 5,
        'taxonomies' => array('brands', 'country'),
        'supports' => array('title', 'editor', 'author', 'thumbnail', 'custom-fields')
    );

    register_post_type('destinations', $args);

Initially I was able to access single page of this post type using single-agences.php but now it is redirecting to 404.

I have checked other answers and found that its a common mistake but other answers were not able to resolve this.
Any help will be wonderful.

Newly registered CPT shows 404 because, the register_post_type() doesn’t flush the rewrite rules. So it’s up to you, whether you want to do it manually or automatically.

Manually:

Get to /wp-admin/, then Settings » Permalinks, and then just hit the Save Changes button to flush the rewrite rules.

Automatically:

You can flush the rewrite rules using flush_rewrite_rules() function. But as register_post_type() is called in init hook, it will fire every time when the init hook will fire. The same thing the codex is saying also:

This function is useful when used with custom post types as it allows for automatic flushing of the WordPress rewrite rules (usually needs to be done manually for new custom post types). However, this is an expensive operation so it should only be used when absolutely necessary.

That’s why it’s better to hook the thing to something that fire once, and that flush rules when necessary only. As @cybmeta already showed that to you. But you can follow @bainternet’s approach as well:

/**
 * To activate CPT Single page
 * @author  Bainternet
 * @link http://en.bainternet.info/2011/custom-post-type-getting-404-on-permalinks
 * ---
 */
$set = get_option( 'post_type_rules_flased_mycpt' );
if ( $set !== true ){
    flush_rewrite_rules( false );
    update_option( 'post_type_rules_flased_mycpt', true );
}

He is saving a value to options table only for your post type. And if the value is not there, he’s flushing rewrite rules. If it’s there, he’s not doing it.

But please note, it’s actually making a db call every time (if not cached). So, I’d prefer hooking the code after_setup_theme for theme, or register_activation_hook for plugin.

Bonus

While debugging rewrite rules, plugin like these could be very helpful:

• Rewrite Rules Inspector by Automattic
• Rewrite Rule Testing by Matthew Boynes
• Debug Bar Rewrite Rules by Frédéric GILLES