Assuming your custom taxonomy is called artist (and you don’t override the slug in the rewrite parameter) you can use the rewrite tag %artist%. WordPress implements almost every functionality to use those rewrite tags in post permalinks. There are only a few small adaptations necessary.

Building the Permalink

First, you’ll need to use the post_link filter to replace a custom »tag« in your request structure:

/**
 * replace the '%artist%' tag with the first 
 * term slug in the artist taxonomy
 * 
 * @wp-hook post_link
 * @param string $permalink
 * @param WP_Post $post
 * @return string
 */
function wpse_56769_post_link( $permalink, $post ) {

    $default_term = 'no_artist';
    $terms = wp_get_post_terms( $post->ID, 'artist' );
    if ( ! empty( $terms ) && ! is_wp_error( $terms ) )
        $term = current( $terms )->slug;
    else
        $term = $default_term;

    $permalink = str_replace( '%artist%', $term, $permalink );

    return $permalink;
}
add_filter( 'post_link', 'wpse_56769_post_link', 10, 2 );

This function (wpse_56769_post_link):

• defines a default term slug (no_artist) which is used as fallback if the post as no assigned terms in the artist taxonomy,
• fetches the first assigned term (in alphabetical order) of the artist taxonomy,
• replaces the tag %artist% with the slug of this term.

Now, go to the menu Settings → Permalinks, choose the option »Custom Structure« and write in: /%artist%/%postname%/.

In the result, a post permalink should look like this:

Now that the post permalinks inkludes the first artist term slug, let’s have a look to the routing.

Update the permalinks (Routing)

You will notice, that the permalink is resolved correctly to the single post. Unfortunately, page permalinks are broken.

To solve this problem, you don’t necessarily need to alter the rewrite rules. The only thing we need to do is to change the internal state of WP_Rewrite. The property WP_Rewrite::use_verbose_page_link needs to be set to TRUE. (This is the internal behaviour of WP_Rewrite when using %category% or %author% tags as base for post permalinks.)

/**
 * set WP_Rewrite::use_verbose_page_rules to TRUE if %artist%
 * is used as the first rewrite tag in post permalinks
 * 
 * @wp-hook do_parse_request
 * @wp-hook page_rewrite_rules
 * @global $wp_rewrite
 * @param mixed $pass_through (Unused)
 * @return mixed
 */
function wpse_56769_rewrite_verbose_page_rules( $pass_through = NULL ) {

    $permastruct = $GLOBALS[ 'wp_rewrite' ]->permalink_structure;
    $permastruct = trim( $permastruct, '/%' );
    if ( 0 !== strpos( $permastruct, 'artist%' ) )
        return $pass_through;

    $GLOBALS[ 'wp_rewrite' ]->use_verbose_page_rules = TRUE;
    return $pass_through;
}
add_filter( 'page_rewrite_rules', 'wpse_56769_rewrite_verbose_page_rules', PHP_INT_MAX );
add_filter( 'do_parse_request',  'wpse_56769_rewrite_verbose_page_rules', PHP_INT_MAX );

The state has to be changed at two points: do_parse_request because WP::parse_request() asks for this state and page_rewrite_rules for when the rewrite rules gets build.

Now, the routing is fixed and page permalinks works well. (After flushing the permalinks once again.)

Handle the no_artist pseudo term

One last thing on the no_artist thing: If the post really is not assigned to any term of the artist taxonomy, the permalink is parsed to the following query variables:

name   => 'sample_post'
artist => 'no_artist'
page   => ''

This should lead to a 404 because the term doesn’t exists. As the post’s name should be unique we can remove the artist query variable on the request filter:

/**
 * check for existing artist and set query to 404 if necessary
 *
 * @wp-hook parse_query
 * @param array $request_vars
 * @return array
 */
function wpse_56769_request_vars( $request_vars ) {

    if ( ! isset( $request_vars[ 'artist' ] ) )
        return $request_vars;

    if ( ! isset( $request_vars[ 'name' ] ) )
        return $request_vars;

    if ( 'no_artist' == $request_vars[ 'artist' ] )
        unset( $request_vars[ 'artist' ] );

    return $request_vars;
}
add_filter( 'request', 'wpse_56769_request_vars' );

With that filter, a post like http://wordpress.dev/no_artist/sample-post/ will be found properly.