Found the answer (via)
Instead of using the function I added an action to “wp_loaded”, that makes sure that it gets loaded before any headers are sended.
<?php
add_action ('wp_loaded', 'my_custom_redirect');
function my_custom_redirect() {
if ( isset( $_POST['subscribe'] ) ) {
$redirect="http://example.com/redirect-example-url.html";
wp_redirect($redirect);
exit;
}
}
?>