diff --git a/htrace-core/src/main/java/org/apache/htrace/Span.java b/htrace-core/src/main/java/org/apache/htrace/Span.java
index 71164d4..b28ff8c 100644
--- a/htrace-core/src/main/java/org/apache/htrace/Span.java
+++ b/htrace-core/src/main/java/org/apache/htrace/Span.java
@@ -111,12 +111,6 @@
   void addKVAnnotation(String key, String value);
 
   /**
-   * Add a data annotation associated with this span
-   */
-  @Deprecated
-  void addKVAnnotation(byte[] key, byte[] value);
-
-  /**
    * Add a timeline annotation associated with this span
    */
   void addTimelineAnnotation(String msg);
diff --git a/htrace-core/src/main/java/org/apache/htrace/Trace.java b/htrace-core/src/main/java/org/apache/htrace/Trace.java
index ef07687..2d8bff5 100644
--- a/htrace-core/src/main/java/org/apache/htrace/Trace.java
+++ b/htrace-core/src/main/java/org/apache/htrace/Trace.java
@@ -158,17 +158,6 @@
   }
 
   /**
-   * Adds a data annotation to the current span if tracing is currently on.
-   */
-  @Deprecated
-  public static void addKVAnnotation(byte[] key, byte[] value) {
-    Span s = currentSpan();
-    if (s != null) {
-      s.addKVAnnotation(key, value);
-    }
-  }
-
-  /**
    * Annotate the current span with the given message.
    */
   public static void addTimelineAnnotation(String msg) {
diff --git a/htrace-core/src/main/java/org/apache/htrace/impl/MilliSpan.java b/htrace-core/src/main/java/org/apache/htrace/impl/MilliSpan.java
index 8544867..ffec117 100644
--- a/htrace-core/src/main/java/org/apache/htrace/impl/MilliSpan.java
+++ b/htrace-core/src/main/java/org/apache/htrace/impl/MilliSpan.java
@@ -257,16 +257,6 @@
   }
 
   @Override
-  public void addKVAnnotation(byte[] key, byte[] value)  {
-    // TODO: remove this method
-    try {
-      addKVAnnotation(new String(key, "UTF-8"), new String(value, "UTF-8"));
-    } catch (UnsupportedEncodingException e) {
-      throw new RuntimeException(e);
-    }
-  }
-
-  @Override
   public void addKVAnnotation(String key, String value) {
     if (traceInfo == null)
       traceInfo = new HashMap<String, String>();
diff --git a/htrace-hbase/src/test/java/org/apache/htrace/impl/TestHBaseSpanReceiver.java b/htrace-hbase/src/test/java/org/apache/htrace/impl/TestHBaseSpanReceiver.java
index 549fddb..0f8eaf5 100644
--- a/htrace-hbase/src/test/java/org/apache/htrace/impl/TestHBaseSpanReceiver.java
+++ b/htrace-hbase/src/test/java/org/apache/htrace/impl/TestHBaseSpanReceiver.java
@@ -208,9 +208,6 @@
     }
 
     @Override
-    public void addKVAnnotation(byte[] key, byte[] value) {}
-
-    @Override
     public void addKVAnnotation(String key, String value) {}
 
     @Override