Add custom taxonomy term in the singular CPT entry permalinks. Source: http://wordpress.stackexchange.com/a/5313/14380. Below is an example for Portfolio. Before: http://d.pr/i/Wt6r, After: http://d.pr/i/QhHN. Make you save changes at Settings > Permalinks.

functions.php

add_action( 'init', 'vc_portfolio_init' );
/**
 * Register a portfolio post type.
 *
 * @link http://codex.wordpress.org/Function_Reference/register_post_type
 */
function vc_portfolio_init() {
	$labels = array(
		'name'               => _x( 'Portfolio', 'post type general name', 'your-plugin-textdomain' ),
		'singular_name'      => _x( 'Portfolio Item', 'post type singular name', 'your-plugin-textdomain' ),
		'menu_name'          => _x( 'Portfolio', 'admin menu', 'your-plugin-textdomain' ),
		'name_admin_bar'     => _x( 'Portfolio Item', 'add new on admin bar', 'your-plugin-textdomain' ),
		'add_new'            => _x( 'Add New Item', 'book', 'your-plugin-textdomain' ),
		'add_new_item'       => __( 'Add New Portfolio Item', 'your-plugin-textdomain' ),
		'new_item'           => __( 'Add New Portfolio Item', 'your-plugin-textdomain' ),
		'edit_item'          => __( 'Edit Portfolio Item', 'your-plugin-textdomain' ),
		'view_item'          => __( 'View Item', 'your-plugin-textdomain' ),
		'all_items'          => __( 'All Portfolio Items', 'your-plugin-textdomain' ),
		'search_items'       => __( 'Search Portfolio', 'your-plugin-textdomain' ),
		'parent_item_colon'  => __( 'Parent Portfolio Item:', 'your-plugin-textdomain' ),
		'not_found'          => __( 'No portfolio items found.', 'your-plugin-textdomain' ),
		'not_found_in_trash' => __( 'No portfolio items found in Trash.', 'your-plugin-textdomain' )
	);

	$args = array(
		'labels'             => $labels,
		'description'        => __( 'Description.', 'your-plugin-textdomain' ),
		'public'             => true,
		'publicly_queryable' => true,
		'show_ui'            => true,
		'show_in_menu'       => true,
		'query_var'          => true,
		// 'rewrite'            => array( 'slug' => 'portfolio' ),
		'rewrite'            => array( 'slug' => 'portfolio/%portfolio_category%' ),
		'capability_type'    => 'post',
		'has_archive'        => true,
		'hierarchical'       => false,
		'menu_position'      => null,
		'supports'           => array( 'title', 'editor', 'author', 'thumbnail', 'excerpt', 'comments' )
	);

	register_post_type( 'portfolio', $args );
}

// hook into the init action and call vc_portfolio_taxonomy when it fires
add_action( 'init', 'vc_portfolio_taxonomy', 0 );
/**
 * create Portfolio Categories taxonomy for the post type "portfolio".
 */
function vc_portfolio_taxonomy() {
	// Add new taxonomy, make it hierarchical (like categories)
	$labels = array(
		'name'              => _x( 'Portfolio Categories', 'taxonomy general name' ),
		'singular_name'     => _x( 'Portfolio Category', 'taxonomy singular name' ),
		'search_items'      => __( 'Search Portfolio Categories' ),
		'all_items'         => __( 'All Portfolio Categories' ),
		'parent_item'       => __( 'Parent Portfolio Category' ),
		'parent_item_colon' => __( 'Parent Portfolio Category:' ),
		'edit_item'         => __( 'Edit Portfolio Category' ),
		'update_item'       => __( 'Update Portfolio Category' ),
		'add_new_item'      => __( 'Add New Portfolio Category' ),
		'new_item_name'     => __( 'New Portfolio Category Name' ),
		'menu_name'         => __( 'Portfolio Categories' ),
	);

	$args = array(
		'hierarchical'      => true,
		'labels'            => $labels,
		'show_ui'           => true,
		'show_admin_column' => true,
		'query_var'         => true,
		'rewrite'           => array( 'slug' => 'portfolio-category' ),
	);

	register_taxonomy( 'portfolio_category', array( 'portfolio' ), $args );

}

/**
 * Inject term slug into custom post type permastruct.
 *
 * @link   http://wordpress.stackexchange.com/a/5313/1685
 *
 * @param  string  $link
 * @param  WP_Post $post
 * @return array
 */
function wpse_5308_post_type_link( $link, $post ) {
	if ( $post->post_type === 'portfolio' ) {
		if ( $terms = get_the_terms( $post->ID, 'portfolio_category' ) )
			$link = str_replace( '%portfolio_category%', current( $terms )->slug, $link );
	}

	return $link;
}

add_filter( 'post_type_link', 'wpse_5308_post_type_link', 10, 2 );

References:

codex.wordpress.org/Function_Reference/register_post_type#Example

codex.wordpress.org/Function_Reference/register_taxonomy#Example